A digital signature, like a handwritten signature, is affixed to a message as proof of authenticity that the message came from a single entity associated with the signature. Two widely used encryption protocols that can be used to create digital signatures include RSA invented by Rivest, Shamir and Adleman, and the Digital Signature Algorithm (DSA) promulgated by the National Institute of Standards and Technology (NIST). RSA and DSA are described in the reference Applied Cryptography, Protocols, Algorithms, and Source Code in C, by Bruce Schneier, 1996, John Wiley & Sons, New York. The DSA is used as the basis of the government Digital Signature Standard (DSS). Use of DSA is required in many popular network security protocols such as Secure Sockets Layer (SSL) and Internet security protocol (IPSec).
Both RSA and DSA employ public key cryptography techniques based on two keys known as a public key and a private key. The two keys are mathematically related, but the private key cannot be determined from the public key. In a system implementing public key technology, each party has its own public/private key pair. The public key can be known by anyone; however, no one should be able to modify it. The private key is kept secret. Its use should be controlled by its owner and it should be protected against modification as well as disclosure.
In general, in public key cryptography, a sender uses the recipient's public key to encrypt a plaintext message; the resulting encrypted message is known as ciphertext. The plaintext may comprise data for text, voice, images, video, or any other data. The ciphertext is sent to a recipient. The recipient can decrypt the message by providing the recipient's private key to a decryption algorithm that processes the message. Because deriving either party's private key from either party's public key is mathematically impractical, a malicious party cannot practically decrypt the message.
To affix a digital signature to a message, a digest of the message is created, the digest is encrypted, resulting in a digital signature. The digital signature is attached to the message, which may be either plaintext or ciphertext, and sent along with the message. In one approach, the message digest is generated using a one-way hash function such as Secure Hash Algorithm (SHA) or MD5. Such functions generate a numeric hash value that is the same every time the same input is passed to the hash function, but produces a different hash when even a slightly different input is passed. It is practically impossible to generate a second sensible input stream that produces the same hash as a different first input stream. The hash practically guarantees that the signature is associated with a particular document.
The security of both RSA and DSA lies in the mathematical difficulty in factoring large integer values (whole numbers with hundreds of decimal digits). Factoring a particular integer means determining the unique set of prime numbers that, multiplied together, form the particular integer. A prime number is a number that has as factors only the number itself and the number one. Both RSA and DSA also employ modulo arithmetic in which intermediate and final results are expressed as an integer in the range from 0 to m−1 for a number m called a modulus. The modulo operation is here represented by the term “mod.” The modulo operation has two parameters, the modulus m and an integer a, and one result, the integer b such that a=b+k*m for some integer k. Effectively, the output b of the modulo operation is the remainder, or residue, of dividing the input integer a by the modulus m. If a is less than m, then b is the same as a. The modulo operation is herein stated as “a modulo m equals b” and written asa mod m=b  (1).Alternatively, this is stated as “a is equivalent to b modulo m” and written asa≡b[mod m]  (2).where [mod m] in square brackets indicates the immediately preceding number or variable is the output of the modulo operation. That is, the integer b always lies between 0 and m−1, whereas the integer a need not. In many cases, the modulus m is related to the size in binary digits (bits) of the field used to store the integer.
Both the RSA and DSA algorithms include at least one step that involves obtaining the multiplicative inverse, modulo m, of an integer a. The multiplicative inverse modulo m of a is represented by a−1. By definition,(a*a−1)mod m=1  (3)For example, for modulus 11, the multiplicative inverse of 3 is 4 because(3*4)mod 11=(12)mod 11=1  (4).The values 15 and 26, which also yield 1, are equivalent to 4 [mod 11].
In conventional systems implementing RSA and DSA, the extended Euclidean algorithm (EEA) is used to compute the multiplicative inverse of an integer a modulo m. The EEA is iterative and can be slow for large numbers. Both RSA and DSA use very large numbers, some numbers expressed with over a thousand bits. Most computations on digital computers are based on numbers expressed in fewer bits, such as 8, 16 or 32 bits.
To increase the speed of the RSA and DSA algorithms, special purpose hardware is sometimes configured to perform some or all of the steps of the algorithms. Such hardware typically takes the form of an application specific integrated circuit (ASIC), a chip, which is composed of separate blocks of circuitry that each performs a certain combination of one or more steps of the computation. The blocks of circuitry are connected so that the output of one block is fed as input to another block. At many steps, a set of parallel connections between blocks is devoted to pass every binary digit (bit) of input and output during each clock cycle. Efficient, thoroughly tested, small footprint blocks have been developed for several modulo computations. For example, existing blocks are available for modulo multiplication (MM) that outputs (a*b) mod m for inputs a, b, m, and for modulo exponentiation (ME) that outputs (ba) mod m for inputs a, b, m.
A block is needed for computing the modulo multiplicative inverse (MI) that outputs (a−1) mod m for inputs a, m. It is estimated that an MI block that implements the EEA for a DSA or RSA application would take significantly more gates on an integrated circuit than the existing ME block. For example, it may take 25% more gates to implement EEA than are taken in the existing ME block. Because the inputs and outputs are large (between 512 and 1024 bits in the DSA algorithm, so some ASICs are designed to handle 2000 bits or more), the 25% additional gates are on the order of about one million extra gates. The extra area on a chip (“chip real estate”) taken by the extra gates limits the number of blocks that can be placed on that chip and therefore limits the number of instances that may be placed on that chip. This then limits the number of messages that can be processed in parallel by any chip or network device built using the chip.
Furthermore, the developmental effort required designing, fabricating, testing, revising, and certifying a new block is a major undertaking even for industry leaders in network device manufacture. The extra effort can significantly increase the time-to-market and impose a competitive disadvantage on the manufacturer that is forced to take the extra development steps.
Based on the foregoing, there is a clear need for an improved MI block that computes a modulo multiplicative inverse and can make use of existing blocks of circuitry for digital signature processing.
In particular, there is a need for a multiplicative inverse block that consumes less area on a chip and incurs fewer developmental costs than an implementation of the EEA.